#include <stdio.h>
#include <stdlib.h>

typedef int ElemType; // 自定义元素类型（可根据需求修改，如char、float等）

typedef struct LNode
{
  ElemType data;      // 数据域：存储元素值
  struct LNode *next; // 指针域：指向下一个节点
} LNode, *LinkList;   // LNode为节点类型，LinkList为节点指针类型，用于表示链表的头指针

// 1. 创建链表
void CreateList_L(LinkList *L, int n)
{
  // 链表的头节点初始化
  *L = (LinkList)malloc(sizeof(LNode)); // 修改main函数中的L指针
  if (*L == NULL)
  {
    printf("Memory allocation failed!\n");
    return;
  }
  (*L)->next = NULL;

  printf("请输入%d个节点的数据值：\n", n);
  for (int i = 0; i < n; i++)
  {
    LNode *p = (LNode *)malloc(sizeof(LNode));
    if (p == NULL)
    {
      printf("Memory allocation failed!\n");
      return;
    }
    // printf("第%d个节点: ", i + 1);
    scanf("%d", &p->data);

    p->next = (*L)->next; // 新节点的next指向当前头节点的后继
    (*L)->next = p;       // 头节点的next指向新节点
  }
}

// 2. 遍历链表
void TraverseList(LinkList L)
{
  LNode *p = L->next; // p指向第一个元素节点
  while (p != NULL)
  {
    printf("%d ", p->data); // 打印当前节点的元素值
    p = p->next;            // 指针后移，访问下一个节点
  }
  printf("\n");
}

// 4. 按位置插入元素
int InsertElem(LinkList L, int pos, ElemType e)
{
  if (pos < 1)
    return 0; // 位置不合法（pos最小为1）

  LNode *p = L; // p从“头结点”开始
  int j = 0;    // 记录当前是第几个节点

  // 找到第pos-1个节点（插入位置的前驱节点）
  while (p != NULL && j < pos - 1)
  {
    p = p->next;
    j++;
  }

  if (p == NULL)
    return 0; // 位置超出链表范围

  // 为新节点分配内存并插入
  LNode *newNode = (LNode *)malloc(sizeof(LNode));
  if (newNode == NULL)
  {
    printf("Memory allocation failed!\n");
    return 0;
  }
  newNode->data = e;       // 新节点存入值
  newNode->next = p->next; // 新节点的next指向“前驱节点的原后继”
  p->next = newNode;       // 前驱节点的next指向新节点
  return 1;                // 插入成功
}

// 4.1 函数功能：删除链表中所有值为val的节点，返回新的头节点
LinkList DeleteElemByVal(LinkList L, ElemType val)
{
  // 创建哑节点，简化头节点删除的特殊情况
  LNode *dummy = (LNode *)malloc(sizeof(LNode));
  if (dummy == NULL)
  {
    // 内存分配失败，返回原链表
    return L;
  }
  dummy->next = L;        // 哑节点指向原头节点
  LNode *current = dummy; // 遍历指针从哑节点开始

  // 遍历链表，检查当前节点的下一个节点是否需要删除
  while (current->next != NULL)
  {
    if (current->next->data == val)
    {
      // 找到需要删除的节点，保存待删除节点
      LNode *temp = current->next;
      // 跳过待删除节点
      current->next = current->next->next;
      // 释放待删除节点的内存
      free(temp);
    }
    else
    {
      // 不需要删除时，指针后移
      current = current->next;
    }
  }

  // 保存新的头节点（哑节点的下一个节点）
  LNode *newHead = dummy->next;
  // 释放哑节点的内存（避免内存泄漏）
  free(dummy);
  // 返回新的头节点
  return newHead;
}

int main()
{
  LinkList L; // L是链表头指针
  int n, pos, e;

  // ---------- 测试：创建链表 ----------
  printf("请输入要创建的链表节点个数：");
  scanf("%d", &n);
  CreateList_L(&L, n);

  printf("创建的链表：");
  TraverseList(L);

  // ---------- 新增测试：按值删除元素 ----------
  printf("请输入要按值删除的元素：");
  scanf("%d", &e);
  printf("按值删除前链表：");
  TraverseList(L);
  LinkList newHead = DeleteElemByVal(L, e);
  printf("按值删除后链表：");
  TraverseList(newHead);
  // 直接打印头节点信息
  printf("按值删除后链表的头节点信息：\n");
  printf("  头节点地址：%p\n", (void *)newHead);
  if (newHead != NULL)
  {
    printf("  头节点data字段值：%d\n", newHead->data);
    printf("  头节点next指针：%p\n", (void *)newHead->next);

    // 如果你想看第一个数据节点的信息
    if (newHead->next != NULL)
    {
      printf("  第一个数据节点地址：%p\n", (void *)newHead->next);
      printf("  第一个数据节点data字段值：%d\n", newHead->next->data);
    }
  }

  return 0;
}